package com.github.hgkmail.hello.leetcode101.pointer.tree;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;
import com.github.hgkmail.hello.leetcode101.base.TreeNode;

//双重递归：1.遍历节点 2.判断树是否相同，时间复杂度O(N^2)。
public class LC572SubtreeOfAnotherTree {
    //二叉树是否相同
    public boolean isSame(TreeNode root1, TreeNode root2) {
        if (root1==null && root2==null) {
            return true;
        }
        if (root1==null || root2==null) {
            return false;
        }
        if (root1.val!= root2.val) {
            return false;
        }
        return isSame(root1.left, root2.left) && isSame(root1.right, root2.right);
    }
    public boolean dfs(TreeNode root, TreeNode subRoot) {
        if (isSame(root, subRoot)) {
            return true;
        }
        boolean ret=false;
        if (root.left!=null) {
            ret = dfs(root.left, subRoot);
        }
        if (ret) {
            return true;
        }
        if (root.right!=null) {
            ret = dfs(root.right, subRoot);
        }
        return ret;
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (subRoot==null) {
            return true;
        }
        if (root==null) {
            return false;
        }
        return dfs(root, subRoot);
    }

    public static void main(String[] args) {
        TreeNode root= CommonUtil.deserializeBinaryTree("3,4,1,#,#,2,#,#,5,#,#");
        TreeNode subRoot= CommonUtil.deserializeBinaryTree("4,1,#,#,2,#,#");
        System.out.println(new LC572SubtreeOfAnotherTree().isSubtree(root, subRoot));
    }
}
